class Solution {
public:
    vector<int> ret;
    vector<int> ans;
    vector<int> path;
    void mergeSort(vector<int>& s,int l,int r,vector<int>& temp){
        if(l >= r) return;
        int mid = (l + r) >> 1;
        mergeSort(s,l,mid,temp);
        mergeSort(s,mid+1,r,temp);
        
        int i = l,j = mid+1,index = l;
        
        
        while(i <= mid && j <= r){
            if(s[i] <= s[j]){
                ret[ans[i]] += index - i;
                
                temp[index] = s[i];
                path[index] = ans[i];
               
                index++;
                i++;
            }else{
                temp[index] = s[j];
                path[index] = ans[j];
            
                index++;
                j++;
            }
        }
        
        while(i <= mid){
            ret[ans[i]] += index - i;
            temp[index] = s[i];
            path[index] = ans[i];
                
            index++;
            i++;
        }
        while(j <= r){
            temp[index] = s[j];
            path[index] = ans[j];
            index++;
            j++;
        }
        
         for (int k = l; k <= r; ++k){
             
            ans[k] = path[k];
            s[k] = temp[k];
        }
      
    }
    vector<int> countSmaller(vector<int>& nums) {
        ret.resize(nums.size());
        vector<int> temp(nums.size());
        ans.resize(nums.size());
        path.resize(nums.size());
        
        for(int i = 0;i < nums.size();i++){
            ans[i] = i;
        }
        
        mergeSort(nums,0,nums.size()-1,temp);
        
        return ret;
    }
};
